%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A positive integer $n$ representing the order of $K_n$, with
  vertex set $V = \{0, 1, \dots, n-1\}$.
\Ensure A random spanning tree of $K_n$.
%%
%% algorithm body
\If{$n = 1$}
  \State \Return $K_1$
\EndIf
\State $P \gets$ random permutation of $V$
\State $T \gets$ null tree
\For{$i \gets 1, 2, \dots, n-1$}
  \State $j \gets$ random element from $\{0, 1, \dots, i-1\}$
  \State add edge $(P[j],\, P[i])$ to $T$
\EndFor
\State \Return $T$
\end{algorithmic}
